<!DOCTYPE html>
<!-- saved from url=(0110)https://www.zhihu.com/question/23995189/answer/613096905?utm_source=qq&utm_medium=social&utm_oi=27836152807424 -->
<html id="html" data-evernote-id="0" class="js-evernote-checked"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><script type="text/javascript" src="chrome-extension://pioclpoplcdbaefihamjohnefbikjilc/BrowserFrameLoader.js"></script><style type="text/css" data-evernote-originating-url="chrome-extension://pioclpoplcdbaefihamjohnefbikjilc/ClearlyReformatStyles.css">
/* general */
/* ======= */

    html, body { background-color: transparent; }

/* main */
/* ==== */

    /* z order */
    #background { z-index: 100; }
    #box { z-index: 200; }

    /* containers */
    html.readableVisible { overflow-y: scroll; }
    #background { position: fixed; top: 0; right: 0; width: 100%; height: 100%; }
    #box, .setBoxWidth { padding-left: 2em; padding-right: 2em; margin-left: auto; margin-right: auto; position: relative; }
    #box_inner, .setBoxWidthInner { position: relative; margin-left: -25px; margin-right: 25px; }
    #text { position: relative; }
    
/* text */
/* ==== */

    #text #articleHeader { margin-bottom: 0; }
    #text #articleHeader__title { padding: 0; margin: 0; }
    #text #articleHeader__author { padding: 0; margin: 0; }
    #text #articleHeader__date { padding: 0; margin: 0; }
    #text #articleHeader a { text-decoration: none }

    #text p:last-child, 
    #text div:last-child, 
    #text blockquote:last-child, 
    #text table:last-child { margin-bottom: 0 !important; } 

    #text pre { width: auto; }

    /* containers */
    /* ========== */

        #text div.readableLargeObjectContainer { display: block; text-align: center; }
        #text div.readableLargeObjectContainer > object,
        #text div.readableLargeObjectContainer > embed,
        #text div.readableLargeObjectContainer > iframe
            { display: block; margin-left:auto; margin-right: auto; }
    
        #text div.readableLargeImageContainer { display: block; text-align: center; }
        #text div.readableLargeImageContainer img { display: block; max-width: 100%; }
        #text div.readableLargeImageContainer.float { float: left; margin-right: 1em; }
    
        #text a.readableLinkWithLargeImage:link { display: block; margin: 0; padding: 0; background-color: transparent; }
        #text a.readableLinkWithLargeImage:link div.readableLargeImageContainer { margin: 0; }
        #text a.readableLinkWithLargeImage:link div.readableLargeImageContainer.float { margin-right: 1em; }

    /* pages */
    /* ===== */

        #text div.page { position: relative; }
        #text div.page_content { }
    
    /* page separators */
    /* =============== */

        #text div.separateSection { }
        
        #text div.separator { position: relative; margin: 0; height: 1em; line-height: 1; text-align: center; }
        #text div.separatorLabel { position: relative; z-index: 100; padding: 0 0.5em; display: inline; }
        #text div.separatorLine, #text section::before { 
            position: absolute; left: -4em; top: 50%; z-index: 10;
            width: 100%; padding-left: 4em; padding-right: 4em;
            height: 0.1em; margin: 0; opacity: 0.5;
        }
        
        #text section { position: relative; }
        #text section::before { 
            content: " "; display: block; 
            left: 25%; top: 0; 
            width: 50%;
            padding-left: 0; padding-right: 0;
            opacity: 0.25; 
        }

        #text section:first-child { margin-top: 0 !important; padding-top: 0 !important; }
        #text section:first-child::before { display: none !important; }

        #text #articleHeader + section::before { display: none !important; }
        #text #articleHeader + section { margin-top: 0 !important; padding-top: 0 !important; }

    /* measure */
    /* ======= */
        #text #measure__lineHeight { position: absolute; top: -1000px; left: -1000px; }
        #text #measure__fontSize { position: absolute; top: -1000px; left: -1000px; line-height: 1; }

    /* options */
    /* ======= */

        /* footnote links */
        /* ============== */
        
            #text sup.readableLinkFootnote { vertical-align: super; font-size: 0.875em; }

            #text #footnotedLinks { margin-top: 2em; }
            #text #footnotedLinks li { margin-bottom: 0.5em; }

            /* on print */
            /* ======== */
        
                body.footnote_links__on_print #text sup.readableLinkFootnote { display: none; }
                body.footnote_links__on_print #footnotedLinks { display: none; }
            
                @media print
                {
                    body.footnote_links__on_print #text sup.readableLinkFootnote { display: inline; }
                    body.footnote_links__on_print #footnotedLinks { display: block; }
                }
    
            /* always */
            /* ====== */
        
                body.footnote_links__always #text sup.readableLinkFootnote { display: inline; }
                body.footnote_links__always #footnotedLinks { display: block; }

            /* never */
            /* ===== */
        
                body.footnote_links__never #text sup.readableLinkFootnote { display: none; }
                body.footnote_links__never #footnotedLinks { display: none; }
    
        /* large graphics */
        /* ============== */
    
            /* hide on print */
            /* ============= */
        
                @media print
                {
                    body.large_graphics__hide_on_print #text div.readableLargeObjectContainer,
                    body.large_graphics__hide_on_print #text div.readableLargeImageContainer,
                    body.large_graphics__hide_on_print #text a.readableLinkWithLargeImage
                        { display: none; }
                }
        
            /* hide always */
            /* =========== */
        
                body.large_graphics__hide_always #text div.readableLargeObjectContainer,
                body.large_graphics__hide_always #text div.readableLargeImageContainer,
                body.large_graphics__hide_always #text a.readableLinkWithLargeImage
                    { display: none; }
                        
/* print */
/* ===== */

    @media print
    {
        #box { margin: 0; width: auto; }
        #background { display: none !important; }
    }

body {
  visibility: hidden;
}
body.clearlyReady {
  visibility: visible;
}

#loading {
  background-size: 118px 117px;
  display: none;
  height: 117px;
  left: calc(50% - 59px);
  position: fixed;
  top: calc(50% - 58.5px);
  visibility: visible !important;
  width: 118px;
  z-index: 300;
}
body.clearlyWaiting #loading {
  display: block;
}
body.clearlyReady #loading {
  display: none;
}

@media (min-resolution: 1.5dppx), (-webkit-min-device-pixel-ratio: 1.5) {
  #loading {
  }
}

/* meyer reset -- http://meyerweb.com/eric/tools/css/reset/ , v2.0 | 20110126 | License: none (public domain) */
/* =========== */

    html, body, div, span, applet, object, iframe,
    h1, h2, h3, h4, h5, h6, p, blockquote, pre,
    a, abbr, acronym, address, big, cite, code,
    del, dfn, em, img, ins, kbd, q, s, samp,
    small, strike, strong, sub, sup, tt, var,
    b, u, i, center,
    dl, dt, dd, ol, ul, li,
    fieldset, form, label, legend,
    table, caption, tbody, tfoot, thead, tr, th, td,
    article, aside, canvas, details, embed,
    figure, figcaption, footer, header, hgroup,
    menu, nav, output, ruby, section, summary,
    time, mark, audio, video {
        margin: 0;
        padding: 0;
        border: 0;
        font-size: 100%;
        font: inherit;
        vertical-align: baseline;
    }

    ol, ul { list-style: none; }
    blockquote, q { quotes: none; }
    blockquote:before, blockquote:after,
    q:before, q:after { content: ''; content: none; }
    table { border-collapse: collapse; border-spacing: 0; }

    article, aside, details, figcaption, figure,
    footer, header, hgroup, menu, nav, section { display: block; }


/* styles */
/* ====== */

    /* headings */
    #text h1, #text h2, #text h3, #text h4, #text h5, #text h6 { font-weight: bold; }
    #text h1 { font-size: 35px; /*30 / 16*/ line-height: 35px /* 48 / 30*/ }
    #text h2, #text h3 { font-size: 30px; /*21 / 16*/ line-height: 35px; /*24 / 21*/ margin-top: 35px; /*48 / 21*/ margin-bottom: 25px /*24 / 21*/ }
    #text h3 { font-weight: normal; }
    #text h4 { font-size: 20px;/*18 / 16*/ margin-top: 30px /*48 / 18*/    }
    #text h5, #text h6 { font-size: 16px /*16*/ }

    /* sections */
    #text section { margin-top: 1.5em !important; padding-top: 1.5em !important; }

    /* links */
    #text a { text-decoration: none; }
    #text a:hover, a:active { text-decoration: underline; }

    /* block spacing */
    #text p, #text blockquote, #text div { margin-bottom: 1.5em; }
    #text h1, #text h2, #text h3, #text h4, #text h5, #text h6 { margin-bottom: 1.5em; }
    #text div.separator { padding-top: 1.5em; padding-bottom: 1.5em; }
    #text div.readableLargeImageContainer, #text div.readableLargeObjectContainer, #text figure { margin-bottom: 1em; margin-top:1em; }

    /* blockquote */
    #text blockquote { font-style: italic; border-left: 5px solid; margin-left: 2em; padding-left: 1em; }

    /* lists */
    #text ul, #text ol { margin: 0 0 1.5em 1.5em; }
    #text ol li { list-style-type: inherit; list-style-position: outside; }
    #text ul li { list-style-type: inherit; list-style-position: outside; }

    /* tables */
    #text table { margin-bottom: 1.5em; /*24 / 16*/ font-size: 1em; /* width: 100%; */ }
    #text thead th, #text tfoot th { padding: .25em .25em .25em .4em; text-transform: uppercase; }
    #text th { text-align: left; }
    #text td { vertical-align: top; padding: .25em .25em .25em .4em; }

    /* formatting */
    #text em, #text i { font-style: italic; }
    #text strong, #text b { font-weight: bold; }

    /* preformatted */
    #text pre, #text code, #text tt { font-size: .875em; line-height: 1.714285em; }

    /* some fixes */
    #text h1 { line-height: 35px; font-weight: normal;  margin-bottom: 20px; }
    #text h1 + h2 { margin-top: 4px; margin-bottom: 20px; font-size: 15px; }
    #text p + ul, #text h2 + ul, #text p + ol, #text h2 + ol { margin-top:-1em; }
    #text h3 + ul, #text h4 + ul, #text h5 + ul, #text h6 + ul, #text h3 + ol, #text h4 + ol, #text h5 + ol, #text h6 + ol { margin-top: 10px; }
    #text h2, #text h3 { margin-bottom: 15px; }
    #text hr { border-top: none; border-right: none; border-bottom: 1px solid; border-left: none; }
    #text pre code, #text code pre { font-size: 1.15em; }



</style><style type="text/css" id="optionsCSS">#body { font-family: "PT Serif"; font-size: 16px; line-height: 1.5em; color: #1f0909; text-align: left; } #text { padding-top: 0;padding-bottom: 9em;} #background { background-color: #f3f2ee; } .setTextColorAsBackgroundColor { background-color: #1f0909; } .setBackgroundColorAsTextColor { color: #f3f2ee; } .setBackgroundColor { background-color: #f3f2ee; } .setTextColor { color: #1f0909; } #box, .setBoxWidth { width: 36em; } a { color: #065588; } a:visited { color: #1f0909; } @media print { body.footnote_links__on_print a, body.footnote_links__on_print a:hover { color: #1f0909 !important; text-decoration: none !important; } } body.footnote_links__always a, body.footnote_links__always a:hover { color: #1f0909 !important; text-decoration: none !important; } img { border-color: #1f0909; } a img { border-color: #065588; } a:visited img { border-color: #1f0909; } h1 a, h2 a, a h1, a h2 { color: #1f0909; } h1, h2, h3, h4, h5, h6 { font-family: "PT Serif"; } pre { background-color: #f3f2ee; } pre, code { font-family: Inconsolata; } hr { border-color: #1f0909; } html.rtl #body #text { text-align: right !important; } h1, h2, h3, h4, h5, h6 { text-align: left; } html.rtl h1, html.rtl h2, html.rtl h3, html.rtl h4, html.rtl h5, html.rtl h6 { text-align: right !important; } #text div.separatorLine, #text section::before { background:      -o-linear-gradient(0, #f3f2ee 1%, #1f0909 50%, #f3f2ee 99%); background:    -moz-linear-gradient(0, #f3f2ee 1%, #1f0909 50%, #f3f2ee 99%); background: -webkit-linear-gradient(0, #f3f2ee 1%, #1f0909 50%, #f3f2ee 99%); } </style><style type="text/css" data-evernote-originating-url="https://fonts.googleapis.com/css?family=PT+Serif:regular,bold,italic">/* cyrillic-ext */
@font-face {
  font-family: 'PT Serif';
  font-style: italic;
  font-weight: 400;
  src: local('PT Serif Italic'), local('PTSerif-Italic'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRTQgYoZZY2vCFuvAFT_rC1chb-.woff2) format('woff2');
  unicode-range: U+0460-052F, U+1C80-1C88, U+20B4, U+2DE0-2DFF, U+A640-A69F, U+FE2E-FE2F;
}
/* cyrillic */
@font-face {
  font-family: 'PT Serif';
  font-style: italic;
  font-weight: 400;
  src: local('PT Serif Italic'), local('PTSerif-Italic'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRTQgYoZZY2vCFuvAFT_rm1chb-.woff2) format('woff2');
  unicode-range: U+0400-045F, U+0490-0491, U+04B0-04B1, U+2116;
}
/* latin-ext */
@font-face {
  font-family: 'PT Serif';
  font-style: italic;
  font-weight: 400;
  src: local('PT Serif Italic'), local('PTSerif-Italic'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRTQgYoZZY2vCFuvAFT_rO1chb-.woff2) format('woff2');
  unicode-range: U+0100-024F, U+0259, U+1E00-1EFF, U+2020, U+20A0-20AB, U+20AD-20CF, U+2113, U+2C60-2C7F, U+A720-A7FF;
}
/* latin */
@font-face {
  font-family: 'PT Serif';
  font-style: italic;
  font-weight: 400;
  src: local('PT Serif Italic'), local('PTSerif-Italic'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRTQgYoZZY2vCFuvAFT_r21cg.woff2) format('woff2');
  unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
}
/* cyrillic-ext */
@font-face {
  font-family: 'PT Serif';
  font-style: normal;
  font-weight: 400;
  src: local('PT Serif'), local('PTSerif-Regular'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRVQgYoZZY2vCFuvAFbzr-tdg.woff2) format('woff2');
  unicode-range: U+0460-052F, U+1C80-1C88, U+20B4, U+2DE0-2DFF, U+A640-A69F, U+FE2E-FE2F;
}
/* cyrillic */
@font-face {
  font-family: 'PT Serif';
  font-style: normal;
  font-weight: 400;
  src: local('PT Serif'), local('PTSerif-Regular'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRVQgYoZZY2vCFuvAFSzr-tdg.woff2) format('woff2');
  unicode-range: U+0400-045F, U+0490-0491, U+04B0-04B1, U+2116;
}
/* latin-ext */
@font-face {
  font-family: 'PT Serif';
  font-style: normal;
  font-weight: 400;
  src: local('PT Serif'), local('PTSerif-Regular'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRVQgYoZZY2vCFuvAFYzr-tdg.woff2) format('woff2');
  unicode-range: U+0100-024F, U+0259, U+1E00-1EFF, U+2020, U+20A0-20AB, U+20AD-20CF, U+2113, U+2C60-2C7F, U+A720-A7FF;
}
/* latin */
@font-face {
  font-family: 'PT Serif';
  font-style: normal;
  font-weight: 400;
  src: local('PT Serif'), local('PTSerif-Regular'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRVQgYoZZY2vCFuvAFWzr8.woff2) format('woff2');
  unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
}
/* cyrillic-ext */
@font-face {
  font-family: 'PT Serif';
  font-style: normal;
  font-weight: 700;
  src: local('PT Serif Bold'), local('PTSerif-Bold'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRSQgYoZZY2vCFuvAnt66qfVyvHpA.woff2) format('woff2');
  unicode-range: U+0460-052F, U+1C80-1C88, U+20B4, U+2DE0-2DFF, U+A640-A69F, U+FE2E-FE2F;
}
/* cyrillic */
@font-face {
  font-family: 'PT Serif';
  font-style: normal;
  font-weight: 700;
  src: local('PT Serif Bold'), local('PTSerif-Bold'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRSQgYoZZY2vCFuvAnt66qWVyvHpA.woff2) format('woff2');
  unicode-range: U+0400-045F, U+0490-0491, U+04B0-04B1, U+2116;
}
/* latin-ext */
@font-face {
  font-family: 'PT Serif';
  font-style: normal;
  font-weight: 700;
  src: local('PT Serif Bold'), local('PTSerif-Bold'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRSQgYoZZY2vCFuvAnt66qcVyvHpA.woff2) format('woff2');
  unicode-range: U+0100-024F, U+0259, U+1E00-1EFF, U+2020, U+20A0-20AB, U+20AD-20CF, U+2113, U+2C60-2C7F, U+A720-A7FF;
}
/* latin */
@font-face {
  font-family: 'PT Serif';
  font-style: normal;
  font-weight: 700;
  src: local('PT Serif Bold'), local('PTSerif-Bold'), url(https://fonts.gstatic.com/s/ptserif/v10/EJRSQgYoZZY2vCFuvAnt66qSVys.woff2) format('woff2');
  unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
}
</style><style type="text/css" data-evernote-originating-url="https://fonts.googleapis.com/css?family=Inconsolata:regular,bold,italic">/* vietnamese */
@font-face {
  font-family: 'Inconsolata';
  font-style: normal;
  font-weight: 400;
  src: local('Inconsolata Regular'), local('Inconsolata-Regular'), url(https://fonts.gstatic.com/s/inconsolata/v17/QldKNThLqRwH-OJ1UHjlKGlW5qhWxg.woff2) format('woff2');
  unicode-range: U+0102-0103, U+0110-0111, U+1EA0-1EF9, U+20AB;
}
/* latin-ext */
@font-face {
  font-family: 'Inconsolata';
  font-style: normal;
  font-weight: 400;
  src: local('Inconsolata Regular'), local('Inconsolata-Regular'), url(https://fonts.gstatic.com/s/inconsolata/v17/QldKNThLqRwH-OJ1UHjlKGlX5qhWxg.woff2) format('woff2');
  unicode-range: U+0100-024F, U+0259, U+1E00-1EFF, U+2020, U+20A0-20AB, U+20AD-20CF, U+2113, U+2C60-2C7F, U+A720-A7FF;
}
/* latin */
@font-face {
  font-family: 'Inconsolata';
  font-style: normal;
  font-weight: 400;
  src: local('Inconsolata Regular'), local('Inconsolata-Regular'), url(https://fonts.gstatic.com/s/inconsolata/v17/QldKNThLqRwH-OJ1UHjlKGlZ5qg.woff2) format('woff2');
  unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
}
/* vietnamese */
@font-face {
  font-family: 'Inconsolata';
  font-style: normal;
  font-weight: 700;
  src: local('Inconsolata Bold'), local('Inconsolata-Bold'), url(https://fonts.gstatic.com/s/inconsolata/v17/QldXNThLqRwH-OJ1UHjlKGHiw71m5_zIDQ.woff2) format('woff2');
  unicode-range: U+0102-0103, U+0110-0111, U+1EA0-1EF9, U+20AB;
}
/* latin-ext */
@font-face {
  font-family: 'Inconsolata';
  font-style: normal;
  font-weight: 700;
  src: local('Inconsolata Bold'), local('Inconsolata-Bold'), url(https://fonts.gstatic.com/s/inconsolata/v17/QldXNThLqRwH-OJ1UHjlKGHiw71n5_zIDQ.woff2) format('woff2');
  unicode-range: U+0100-024F, U+0259, U+1E00-1EFF, U+2020, U+20A0-20AB, U+20AD-20CF, U+2113, U+2C60-2C7F, U+A720-A7FF;
}
/* latin */
@font-face {
  font-family: 'Inconsolata';
  font-style: normal;
  font-weight: 700;
  src: local('Inconsolata Bold'), local('Inconsolata-Bold'), url(https://fonts.gstatic.com/s/inconsolata/v17/QldXNThLqRwH-OJ1UHjlKGHiw71p5_w.woff2) format('woff2');
  unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
}
</style><style type="text/css" data-evernote-originating-url="chrome-extension://pioclpoplcdbaefihamjohnefbikjilc/HighlightStyles.css">body.clearly_highlighting_enabled ::-moz-selection {
  background: rgba(246, 238, 150, 0.99);
}

body.clearly_highlighting_enabled ::selection {
  background: rgba(246, 238, 150, 0.99);
}

mark.clearly_highlight_element {
  font-style: inherit !important;
  font-weight: inherit !important;
}

.en-simplified-article mark {
  font-style: unset !important;
}

body.en-simplified-article {
  padding-top: 4.5em;
}

body.clearly_highlighting_enabled mark.clearly_highlight_element {
  background-color: #EAE260;
  transition: background-color 0.4s ease;
  color: black;
}

body.clearly_highlighting_enabled mark.clearly_highlight_element.hovered {
  cursor: pointer;
  background-color: #F0F1F1;
  transition: background-color 0.4s ease;
  /* TODO: found out why border with negative margin make strange space */
  /* border: 1px solid #EDEDED; */
  /* margin: -1px; */
}



</style><link type="text/css" rel="stylesheet" href="chrome-extension://pioclpoplcdbaefihamjohnefbikjilc/HighlightStyles.css"><link type="text/css" rel="stylesheet" href="chrome-extension://pioclpoplcdbaefihamjohnefbikjilc/HighlightStyles.css"><script type="text/javascript" src="chrome-extension://pioclpoplcdbaefihamjohnefbikjilc/FrameSerializer.js"></script></head><body id="body" class="clearlyReady footnote_links__on_print large_graphics__do_nothing en-simplified-article clearly_highlighting_enabled js-evernote-checked" data-evernote-id="1"><div id="bodyContent" class="en-simplified-article js-evernote-checked" data-evernote-id="25"><div id="box" data-evernote-id="3" class="js-evernote-checked"><div id="box_inner" data-evernote-id="4" class="js-evernote-checked"><div id="text" data-evernote-id="5" class="js-evernote-checked"><div id="pages" data-evernote-id="26" class="js-evernote-checked"><div class="page js-evernote-checked" id="page1" data-evernote-id="8"><div class="page_content js-evernote-checked" data-evernote-id="9"><div id="articleHeader" data-evernote-id="6" class="js-evernote-checked"><h1 id="articleHeader__title" data-evernote-id="7" class="js-evernote-checked">(13 条消息) 什么是动态规划（Dynamic Programming）？动态规划的意义是什么？</h1><div id="articleHeader__separator" class="separator js-evernote-checked" data-evernote-id="10"><div class="separatorLine setTextColorAsBackgroundColor js-evernote-checked" data-evernote-id="11"></div></div></div><h2 data-evernote-id="27" class="js-evernote-checked">0. intro</h2><p data-evernote-id="28" class="js-evernote-checked">　　很有意思的问题。以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不应该是这样的。恰好我给入门者讲过四次DP入门，迭代出了一套比较靠谱的教学方法，所以今天跑过来献丑。</p><p data-evernote-id="29" class="js-evernote-checked">　　现在，我们试着自己来一步步“重新发明”DP。</p><h2 data-evernote-id="30" class="js-evernote-checked">1. 从一个生活问题谈起</h2><p data-evernote-id="31" class="js-evernote-checked">　　先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，<b data-evernote-id="32" class="js-evernote-checked">需要用到尽量少的钞票。</b></p><p data-evernote-id="33" class="js-evernote-checked">　　依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。</p><p data-evernote-id="34" class="js-evernote-checked">　　这种策略称为“<b data-evernote-id="35" class="js-evernote-checked">贪心</b>”：假设我们面对的局面是“需要凑出w”，<b data-evernote-id="36" class="js-evernote-checked">贪心策略会<u data-evernote-id="37" class="js-evernote-checked">尽快</u>让w变得更小</b>。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。</p><p data-evernote-id="38" class="js-evernote-checked">　　但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：<br>　　15=1×11+4×1    （贪心策略使用了5张钞票）<br>　　15=3×5               （正确的策略，只用3张钞票）<br>　　为什么会这样呢？贪心策略错在了哪里？</p><p data-evernote-id="39" class="js-evernote-checked"><b data-evernote-id="40" class="js-evernote-checked">　　鼠目寸光。</b><br>　　刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。<br>　　在这里我们发现，贪心是一种<b data-evernote-id="41" class="js-evernote-checked">只考虑眼前情况</b>的策略。</p><p data-evernote-id="42" class="js-evernote-checked">　　那么，现在我们怎样才能避免鼠目寸光呢？</p><p data-evernote-id="43" class="js-evernote-checked">　　如果直接暴力枚举凑出w的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们现在来尝试找一下性质。</p><p data-evernote-id="44" class="js-evernote-checked">　　重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。</p><p data-evernote-id="45" class="js-evernote-checked">　　那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？<br>　　明显<img src="./equation" width="251" height="26" alt="[公式]" data-evernote-id="46" class="js-evernote-checked"> ，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。<br>　　依次类推，马上可以知道：如果我们用5来凑出15，cost就是<img src="./equation(1)" width="197" height="26" alt="[公式]" data-evernote-id="47" class="js-evernote-checked"> 。</p><p data-evernote-id="48" class="js-evernote-checked">　　那么，现在w=15的时候，我们该取那种钞票呢？<b data-evernote-id="49" class="js-evernote-checked">当然是各种方案中，cost值最低的那一个</b>！</p><p data-evernote-id="50" class="js-evernote-checked">　　- 取11：<img src="./equation(2)" width="251" height="26" alt="[公式]" data-evernote-id="51" class="js-evernote-checked"><br>　　- 取5：  <img src="./equation(3)" width="261" height="26" alt="[公式]" data-evernote-id="52" class="js-evernote-checked"><br>　　- 取1：  <img src="./equation(4)" width="261" height="26" alt="[公式]" data-evernote-id="53" class="js-evernote-checked"></p><p data-evernote-id="54" class="js-evernote-checked">　　显而易见，cost值最低的是取5的方案。<b data-evernote-id="55" class="js-evernote-checked">我们通过上面三个式子，做出了正确的决策</b>！</p><p data-evernote-id="56" class="js-evernote-checked">　　这给了我们一个<b data-evernote-id="57" class="js-evernote-checked">至关重要</b>的启示—— <img src="./equation(5)" width="40" height="25" alt="[公式]" data-evernote-id="58" class="js-evernote-checked"> 只与 <img src="./equation(6)" width="258" height="26" alt="[公式]" data-evernote-id="59" class="js-evernote-checked"> 相关；更确切地说：</p><p data-evernote-id="60" class="js-evernote-checked"><img src="./equation(7)" width="418" height="26" alt="[公式]" data-evernote-id="61" class="js-evernote-checked"></p><p data-evernote-id="62" class="js-evernote-checked">　　这个式子是非常激动人心的。我们要求出f(n)，只需要求出几个更小的f值；既然如此，我们从小到大把所有的f(i)求出来不就好了？注意一下边界情况即可。代码如下：</p><figure data-evernote-id="63" class="js-evernote-checked"><div class="readableLargeImageContainer js-evernote-checked" data-evernote-id="12"><img src="./v2-6a5ba74fb90968533ece429ed329c903_r.jpg" data-evernote-id="19" class="js-evernote-checked" width="576" height="243"></div></figure><p data-evernote-id="64" class="js-evernote-checked">　　我们以 <img src="./equation(8)" width="45" height="26" alt="[公式]" data-evernote-id="65" class="js-evernote-checked"> 的复杂度解决了这个问题。现在回过头来，我们看看它的原理：</p><p data-evernote-id="66" class="js-evernote-checked">　　- <img src="./equation(5)" width="40" height="25" alt="[公式]" data-evernote-id="67" class="js-evernote-checked"> 只与<img src="./equation(6)" width="258" height="26" alt="[公式]" data-evernote-id="68" class="js-evernote-checked">的<b data-evernote-id="69" class="js-evernote-checked">值</b>相关。<br>　　-  我们只关心 <img src="./equation(9)" width="43" height="26" alt="[公式]" data-evernote-id="70" class="js-evernote-checked"> 的<b data-evernote-id="71" class="js-evernote-checked">值</b>，不关心是怎么凑出w的。</p><p data-evernote-id="72" class="js-evernote-checked">　　这两个事实，保证了我们做法的正确性。它比起贪心策略，会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”！</p><p data-evernote-id="73" class="js-evernote-checked">　　它与暴力的区别在哪里？我们的暴力枚举了“使用的硬币”，然而这属于冗余信息。我们要的是答案，根本不关心这个答案是怎么凑出来的。譬如，要求出f(15)，只需要知道f(14),f(10),f(4)的值。<b data-evernote-id="74" class="js-evernote-checked">其他信息并不需要。</b>我们舍弃了冗余信息。我们只记录了对解决问题有帮助的信息——f(n).</p><p data-evernote-id="75" class="js-evernote-checked">　　我们能这样干，取决于问题的性质：求出f(n)，只需要知道几个更小的f(c)。<b data-evernote-id="76" class="js-evernote-checked">我们将求解f(c)称作求解f(n)的“子问题”。</b></p><p data-evernote-id="77" class="js-evernote-checked"><b data-evernote-id="78" class="js-evernote-checked">　　这就是DP</b>（动态规划，dynamic programming）.</p><p data-evernote-id="79" class="js-evernote-checked"><b data-evernote-id="80" class="js-evernote-checked">　　将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解</b>。</p><blockquote data-evernote-id="81" class="js-evernote-checked">思考题：请稍微修改代码，输出我们凑出w的<b data-evernote-id="82" class="js-evernote-checked">方案</b>。</blockquote><h2 data-evernote-id="83" class="js-evernote-checked">2. 几个简单的概念</h2><p data-evernote-id="84" class="js-evernote-checked">【无后效性】</p><p data-evernote-id="85" class="js-evernote-checked">　　一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。</p><p data-evernote-id="86" class="js-evernote-checked">　　要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。</p><p data-evernote-id="87" class="js-evernote-checked"><b data-evernote-id="88" class="js-evernote-checked">　　“未来与过去无关”，</b>这就是<b data-evernote-id="89" class="js-evernote-checked">无后效性</b>。</p><p data-evernote-id="90" class="js-evernote-checked">　　（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）</p><p data-evernote-id="91" class="js-evernote-checked">【最优子结构】</p><p data-evernote-id="92" class="js-evernote-checked">　　回顾我们对f(n)的定义：我们记“凑出n所需的<b data-evernote-id="93" class="js-evernote-checked">最少</b>钞票数量”为f(n).</p><p data-evernote-id="94" class="js-evernote-checked">　　f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的<b data-evernote-id="95" class="js-evernote-checked">最优</b>解，我们即可算出w=15的<b data-evernote-id="96" class="js-evernote-checked">最优</b>解。</p><p data-evernote-id="97" class="js-evernote-checked">　　大问题的<b data-evernote-id="98" class="js-evernote-checked">最优解</b>可以由小问题的<b data-evernote-id="99" class="js-evernote-checked">最优解</b>推出，这个性质叫做“最优子结构性质”。</p><p data-evernote-id="100" class="js-evernote-checked">　　引入这两个概念之后，我们如何判断一个问题能否使用DP解决呢？</p><p data-evernote-id="101" class="js-evernote-checked"><b data-evernote-id="102" class="js-evernote-checked">　　能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。</b></p><h2 data-evernote-id="103" class="js-evernote-checked"><b data-evernote-id="104" class="js-evernote-checked">3. DP的典型应用：DAG最短路</b></h2><p data-evernote-id="105" class="js-evernote-checked">　　问题很简单：给定一个城市的地图，所有的道路都是单行道，而且不会构成环。每条道路都有过路费，问您从S点到T点花费的最少费用。</p><figure data-evernote-id="106" class="js-evernote-checked"><div class="readableLargeImageContainer js-evernote-checked" data-evernote-id="18"><img src="./v2-38e9a487997d2eea979097fbc9e9e674_r.jpg" data-evernote-id="20" class="js-evernote-checked" width="523" height="251"></div><figcaption data-evernote-id="107" class="js-evernote-checked">一张地图。边上的数字表示过路费。</figcaption></figure><p data-evernote-id="108" class="js-evernote-checked">　　这个问题能用DP解决吗？我们先试着记从S到P的最少费用为f(P).<br>　　想要到T，要么经过C，要么经过D。从而<img src="./equation(10)" width="321" height="26" alt="[公式]" data-evernote-id="109" class="js-evernote-checked">.</p><p data-evernote-id="110" class="js-evernote-checked">　　好像看起来可以DP。现在我们检验刚刚那两个性质：<br>　　- 无后效性：对于点P，一旦f(P)确定，以后就只关心f(P)的值，不关心怎么去的。<br>　　- 最优子结构：对于P，我们当然只关心到P的最小费用，即f(P)。如果我们从S走到T是 <img src="./equation(11)" width="158" height="23" alt="[公式]" data-evernote-id="111" class="js-evernote-checked"> ，那肯定S走到Q的最优路径是 <img src="./equation(12)" width="111" height="23" alt="[公式]" data-evernote-id="112" class="js-evernote-checked"> 。对一条最优的路径而言，从S走到<b data-evernote-id="113" class="js-evernote-checked">沿途上所有的点（子问题）</b>的最优路径，都是这条大路的一部分。这个问题的最优子结构性质是显然的。</p><p data-evernote-id="114" class="js-evernote-checked">　　既然这两个性质都满足，那么本题可以DP。式子明显为：</p><p data-evernote-id="115" class="js-evernote-checked"><img src="./equation(13)" width="254" height="26" alt="[公式]" data-evernote-id="116" class="js-evernote-checked"></p><p data-evernote-id="117" class="js-evernote-checked">　　其中R为有路通到P的所有的点， <img src="./equation(14)" width="54" height="18" alt="[公式]" data-evernote-id="118" class="js-evernote-checked"> 为R到P的过路费。</p><p data-evernote-id="119" class="js-evernote-checked">　　代码实现也很简单，拓扑排序即可。</p><h2 data-evernote-id="120" class="js-evernote-checked">4. 对DP原理的一点讨论</h2><p data-evernote-id="121" class="js-evernote-checked">【DP的核心思想】</p><p data-evernote-id="122" class="js-evernote-checked">　　DP为什么会快？<br>　　无论是DP还是暴力，我们的算法都是在<b data-evernote-id="123" class="js-evernote-checked">可能解空间</b>内，寻找<b data-evernote-id="124" class="js-evernote-checked">最优解</b>。</p><p data-evernote-id="125" class="js-evernote-checked">　　来看钞票问题。暴力做法是枚举所有的可能解，这是最大的可能解空间。<br>　　DP是枚举<b data-evernote-id="126" class="js-evernote-checked">有希望成为答案的解</b>。这个空间比暴力的小得多。</p><p data-evernote-id="127" class="js-evernote-checked">　　也就是说：DP自带剪枝。</p><p data-evernote-id="128" class="js-evernote-checked">　　DP舍弃了一大堆不可能成为最优解的答案。譬如：<br>　　15 = 5+5+5 被考虑了。<br>　　15 = 5+5+1+1+1+1+1 从来没有考虑过，因为这不可能成为最优解。</p><p data-evernote-id="129" class="js-evernote-checked">　　从而我们可以得到DP的核心思想：<b data-evernote-id="130" class="js-evernote-checked">尽量缩小可能解空间。</b></p><p data-evernote-id="131" class="js-evernote-checked">　　在暴力算法中，可能解空间往往是指数级的大小；如果我们采用DP，那么有可能把解空间的大小降到多项式级。</p><p data-evernote-id="132" class="js-evernote-checked">　　一般来说，解空间越小，寻找解就越快。这样就完成了优化。</p><p data-evernote-id="133" class="js-evernote-checked">【DP的操作过程】</p><p data-evernote-id="134" class="js-evernote-checked">　　一言以蔽之：<b data-evernote-id="135" class="js-evernote-checked">大事化小，小事化了。</b></p><p data-evernote-id="136" class="js-evernote-checked">　　将一个大问题转化成几个小问题；<br>　　求解小问题；<br>　　推出大问题的解。</p><p data-evernote-id="137" class="js-evernote-checked">【如何设计DP算法】</p><p data-evernote-id="138" class="js-evernote-checked">　　下面介绍比较通用的设计DP算法的步骤。</p><p data-evernote-id="139" class="js-evernote-checked">　　首先，把我们面对的<b data-evernote-id="140" class="js-evernote-checked">局面</b>表示为x。这一步称为<b data-evernote-id="141" class="js-evernote-checked">设计状态</b>。<br>　　对于状态x，记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).<br><b data-evernote-id="142" class="js-evernote-checked">找出f(x)与哪些局面有关（记为p）</b>，写出一个式子（称为<b data-evernote-id="143" class="js-evernote-checked">状态转移方程</b>），通过f(p)来推出f(x).</p><p data-evernote-id="144" class="js-evernote-checked">【DP三连】</p><p data-evernote-id="145" class="js-evernote-checked">　　设计DP算法，往往可以遵循DP三连：</p><p data-evernote-id="146" class="js-evernote-checked">　　我是谁？  ——设计状态，表示局面<br>　　我从哪里来？<br>　　我要到哪里去？  ——设计转移</p><p data-evernote-id="147" class="js-evernote-checked">　　设计状态是DP的基础。接下来的设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，<b data-evernote-id="148" class="js-evernote-checked">更新能从x走到的一些解</b>。这种DP也是不少的，我们以后会遇到。</p><p data-evernote-id="149" class="js-evernote-checked">　　总而言之，“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个，就能设计出状态转移方程，从而写代码求解问题。前者又称pull型的转移，后者又称push型的转移。（这两个词是 </p><div data-evernote-id="150" class="js-evernote-checked"><div id="Popover19-toggle" data-evernote-id="13" class="js-evernote-checked"><a href="https://www.zhihu.com/people/31585b1079521ef37391925a95a5d4ba" target="_blank" data-evernote-id="151" class="js-evernote-checked">@阮止雨</a></div></div> 妹妹告诉我的，不知道源出处在哪）<p data-evernote-id="152" class="js-evernote-checked"></p><blockquote data-evernote-id="153" class="js-evernote-checked">思考题：如何把钞票问题的代码改写成“我到哪里去”的形式？<br>提示：求出f(x)之后，更新f(x+1),f(x+5),f(x+11).</blockquote><h2 data-evernote-id="154" class="js-evernote-checked">5. 例题：最长上升子序列</h2><p data-evernote-id="155" class="js-evernote-checked">　　扯了这么多形而上的内容，还是做一道例题吧。</p><p data-evernote-id="156" class="js-evernote-checked">　　最长上升子序列（LIS）问题：给定长度为n的序列a，从a中抽取出一个子序列，这个子序列需要单调递增。问最长的上升子序列（LIS）的长度。<br>　　e.g. 1,5,3,4,6,9,7,8的LIS为1,3,4,6,7,8，长度为6。</p><p data-evernote-id="157" class="js-evernote-checked">　　如何设计状态（我是谁）？</p><p data-evernote-id="158" class="js-evernote-checked">　　我们记 <img src="./equation(15)" width="40" height="26" alt="[公式]" data-evernote-id="159" class="js-evernote-checked"> 为以 <img src="./equation(16)" width="22" height="18" alt="[公式]" data-evernote-id="160" class="js-evernote-checked"> 结尾的LIS长度，那么答案就是 <img src="./equation(17)" width="100" height="26" alt="[公式]" data-evernote-id="161" class="js-evernote-checked"> .</p><p data-evernote-id="162" class="js-evernote-checked">　　状态x从哪里推过来（我从哪里来）？</p><p data-evernote-id="163" class="js-evernote-checked">　　考虑比x小的每一个p：如果 <img src="./equation(18)" width="70" height="23" alt="[公式]" data-evernote-id="164" class="js-evernote-checked"> ，那么f(x)可以取f(p)+1.<br>　　解释：我们把 <img src="./equation(16)" width="22" height="18" alt="[公式]" data-evernote-id="165" class="js-evernote-checked"> 接在 <img src="./equation(19)" width="21" height="21" alt="[公式]" data-evernote-id="166" class="js-evernote-checked"> 的后面，肯定能构造一个以 <img src="./equation(16)" width="22" height="18" alt="[公式]" data-evernote-id="167" class="js-evernote-checked"> 结尾的上升子序列，长度比以 <img src="./equation(19)" width="21" height="21" alt="[公式]" data-evernote-id="168" class="js-evernote-checked"> 结尾的LIS大1.那么，我们可以写出状态转移方程了：</p><p data-evernote-id="169" class="js-evernote-checked"><img src="./equation(20)" width="241" height="39" alt="[公式]" data-evernote-id="170" class="js-evernote-checked"></p><p data-evernote-id="171" class="js-evernote-checked">　　至此解决问题。两层for循环，复杂度 <img src="./equation(21)" width="54" height="28" alt="[公式]" data-evernote-id="172" class="js-evernote-checked"> .</p><figure data-evernote-id="173" class="js-evernote-checked"><div class="readableLargeImageContainer js-evernote-checked" data-evernote-id="14"><img src="./v2-73ea19922aaac11c15dff9146a5c5b41_r.jpg" data-evernote-id="21" class="js-evernote-checked" width="576" height="297"></div></figure><p data-evernote-id="174" class="js-evernote-checked">　　从这三个例题中可以看出，DP是一种思想，一种“大事化小，小事化了”的思想。带着这种思想，DP将会成为我们解决问题的利器。</p><p data-evernote-id="175" class="js-evernote-checked">　　最后，我们一起念一遍DP三连吧——我是谁？我从哪里来？我要到哪里去？</p><h2 data-evernote-id="176" class="js-evernote-checked">6. 习题</h2><p data-evernote-id="177" class="js-evernote-checked">如果读者有兴趣，可以试着完成下面几个习题：</p><p data-evernote-id="178" class="js-evernote-checked">一、请采取一些优化手段，以 <img src="./equation(22)" width="91" height="26" alt="[公式]" data-evernote-id="179" class="js-evernote-checked"> 的复杂度解决LIS问题。</p><p data-evernote-id="180" class="js-evernote-checked">提示：可以参考这篇博客 <a href="https://link.zhihu.com/?target=https%3A//pks-loving.blog.luogu.org/junior-dynamic-programming-dong-tai-gui-hua-chu-bu-ge-zhong-zi-xu-lie" target="_blank" data-evernote-id="181" class="js-evernote-checked">Junior Dynamic Programming--动态规划初步·各种子序列问题</a></p><p data-evernote-id="182" class="js-evernote-checked">二、“按顺序递推”和“记忆化搜索”是实现DP的两种方式。请查阅资料，简单描述“记忆化搜索”是什么。并采用记忆化搜索写出钞票问题的代码，然后完成<a href="https://link.zhihu.com/?target=https%3A//www.luogu.org/problemnew/show/P1541" target="_blank" data-evernote-id="183" class="js-evernote-checked">P1541 乌龟棋 - 洛谷</a> 。</p><p data-evernote-id="184" class="js-evernote-checked">三、01背包问题是一种常见的DP模型。请完成<a href="https://link.zhihu.com/?target=https%3A//www.luogu.org/problemnew/show/P1048" target="_blank" data-evernote-id="185" class="js-evernote-checked">P1048 采药 - 洛谷</a>。</p><p data-evernote-id="186" class="js-evernote-checked">谢谢您看完本文 ⁄(⁄ ⁄ ⁄ω⁄ ⁄ ⁄)⁄</p><p data-evernote-id="15" class="js-evernote-checked">2019.3.3</p></div></div></div><div id="footnotedLinks" class="separateSection js-evernote-checked" data-evernote-id="22"><div id="footnotedLinks__separator" class="separator js-evernote-checked" data-evernote-id="23"><div class="separatorLine setTextColorAsBackgroundColor js-evernote-checked" data-evernote-id="16"></div></div><ol id="footnotedLinks__list" data-evernote-id="187" class="js-evernote-checked"></ol></div><div id="measure__lineHeight" data-evernote-id="24" class="js-evernote-checked">Measure</div><div id="measure__fontSize" data-evernote-id="17" class="js-evernote-checked">Measure</div></div></div></div><div id="background" data-evernote-id="2" class="js-evernote-checked"></div></div><link rel="stylesheet" href="chrome-extension://pioclpoplcdbaefihamjohnefbikjilc/ClearlyReformatStyles.css" type="text/css"></body></html>